package leetcode.code0474;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int m, n;

	public int findMaxForm(String[] strs, int m, int n) {
		int len = strs.length;
		int[][] sizes = new int[len][2];
		for (int i = 0; i < len; i++) {
			int[] size = this.f(strs[i]);
			sizes[i] = size;
		}
		this.m = m;
		this.n = n;
		Integer[][][] dp = new Integer[len + 1][m + 1][n + 1];// [len + 1]
		return this.findMaxForm(sizes, 0, 0, 0, dp);
	}

	private int findMaxForm(int[][] sizes, int index, int zero, int one, Integer[][][] dp) {
		if (index == sizes.length || zero > m || one > n) {
			return 0;
		}
		if (dp[index][zero][one] != null) {
			return dp[index][zero][one];
		}
		int ans1 = this.findMaxForm(sizes, index + 1, zero, one, dp);
		int ans2 = 0;
		int[] cur = sizes[index];
		if (zero + cur[0] <= m && one + cur[1] <= n) {
			ans2 = this.findMaxForm(sizes, index + 1, zero + cur[0], one + cur[1], dp) + 1;
		}
		int ans = Math.max(ans1, ans2);
		dp[index][zero][one] = ans;
		return ans;
	}

	private int[] f(String string) {
		char[] cs = string.toCharArray();
		int z = 0, o = 0;
		for (char element : cs) {
			if (element == '0') {
				o++;
			} else {
				z++;
			}
		}
		return new int[] { o, z };
	}

	@Override
	public void debug1() {
		HelpDebug.compare(4, this.findMaxForm(HelpDebug.str2array2("[\"10\",\"0001\",\"111001\",\"1\",\"0\"]"), 5, 3));
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

//["101","110","0","0","0","0001","1010","01","10110","0011","0","10","11","110","1","10","0","1","00","1","0","010","1","000","0","101","0","11","1","01111","110000","1","01"]
//47
//88

//["0","0","1","1","1","0","1","0","0","1","1","0","1","0","1","0","1","0","0","1","0","1","0","0","1","1","1","0","1","1","0","0","1","1","1","0","1","0","0","0","1","0","1","0","0","1","0","0","1","1","1","1","1","0","0","1","0","1","0","1","1","0","0","0","1","1","1","1","1","1","0","1","1","1","0","0","1","1","0","0","1","1","0","1","0","0","1"]
//93
//91

//["10","0001","111001","1","0"]
//3
//4

}
